package com.khiker.sort;

/**
 * 平均时间复杂度：n^2
 * 最坏时间复杂度：n^2
 * 最好时间复杂度：n
 * 空间复杂度：1
 * 稳定性：稳定
 */
public class Bubble implements Sort {
	@Override
	public int[] sort(int[] array) {
		for (int i = array.length; i > 0; i--) {
			int swap = 0;
			for (int j = 1; j < i; j++) {
				if (array[j - 1] > array[j]) {
					swap(array, j - 1, j);
					swap++;
				}
			}
			if (swap == 0) {
				break;
			}
		}
		return array;
	}


	public static void main(String[] args) {
		Bubble bubble = new Bubble();

		bubble.checkMulti(100);
	}
}
